/*
 * @lc app=leetcode.cn id=1477 lang=typescript
 *
 * [1477] 找两个和为目标值且不重叠的子数组
 */

// @lc code=start
function minSumOfLengths(arr: number[], target: number): number {
  const n = arr.length;
  // 保存区间和为target的左右索引：[l,r]
  const ranges: number[][] = [];
  let l = 0;
  let sum = 0;
  // 统计区间和为target的区间
  for (let r = 0; r < n; r++) {
    sum += arr[r];
    while (sum > target && l <= r) {
      sum -= arr[l];
      l++;
    }
    if (sum === target) {
      ranges.push([l, r]);
    }
  }

  let ans = -1;
  let preIdx = -1;
  let preMin = Number.POSITIVE_INFINITY;
  for (const [l, r] of ranges) {
    // 找到当前元素之前与之不相交的区间
    while (ranges[preIdx + 1][1] < l) {
      preIdx++;
      preMin = Math.min(preMin, ranges[preIdx][1] - ranges[preIdx][0] + 1);
    }
    if (preIdx === -1) continue;
    // 更新答案
    if (ans === -1 || ans > preMin + r - l + 1) {
      ans = preMin + r - l + 1;
    }
  }

  return ans;
}
// @lc code=end
